package com.sicheng.lc.杂题.二叉树;

import leetcode.editor.cn.tree.TreeNode;

import java.util.*;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/19 14:31
 */
public class 重建二叉树 {
    // 缓存中序遍历数组每个值对应的索引
    private Map<Integer, Integer> index = new HashMap<>();

    public TreeNode build(int[] pre, int[] in) {
        for (int i = 0; i < in.length; i++) {
            index.put(in[i], i);
        }
        return build(pre, 0, pre.length - 1, 0);
    }

    private TreeNode build(int[] pre, int l, int r, int in) {
        if (l > r)
            return null;
        TreeNode root = new TreeNode(pre[l]);

        int leftSize = index.get(pre[l]) - in;

        root.left = build(pre, l + 1, l + leftSize, in);
        root.right = build(pre, l + leftSize + 1, r, in + leftSize + 1);
        return root;
    }


    List<Integer> right(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                assert node != null;
                if (node.left != null)
                    deque.offer(node.left);
                if (node.right != null)
                    deque.offer(node.right);

                if (i == size - 1)
                    res.add(node.val);
            }
        }

        return res;
    }


    public static void main(String[] args) {
        重建二叉树 s = new 重建二叉树();
        int[] pre = {1, 2, 4, 5, 3}, in = {4, 2, 5, 1, 3};
        TreeNode root = s.build(pre, in);
        System.out.println(s.right(root));
    }
}
